package huawei;

import sun.reflect.generics.tree.Tree;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        TreeNode root=new TreeNode(pre[0]);
        //第一种 只有一个  情况直接返回根节点
        if(pre.length==1) return root;
        //找到 1 在数组的位置
        int fir_root=0;
        for (int i = 0; i < in.length; i++) {
            if(pre[0]==in[i]){
                fir_root=i; //即在左边需要执行的次数
                break;
            }
        }
        //记录寻找的位置
        //前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
        //如果现在  first
        int val=pre[0];
        TreeNode root_now=root;
        int position=0; //position=0在左边 position=1在右边
        for (int i =1; i < pre.length; i++) {
            //把主根左边全部找完
            fir_root--;
            if(fir_root==0){
                root_now=root;
            }

            for (int j = 0; j < in.length; j++) {
                if(in[j]==val){
                    position=1;
                    break;  //证明这个pre[i]数在val的右边
                }
                if(in[j]==pre[i]) {
                    position=0;
                    break;
                }
            }

            //此时已经找到该点的位置
            if(position==0){
                root_now.left=new TreeNode(pre[i]);
                
                root_now=root_now.left;
            }
            if(position==1){
                root_now.right=new TreeNode(pre[i]);
                root_now=root_now.right;
            }
            val=pre[i];
        }

        return root;
    }
}
